package middle;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。
 * 找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FindFirstAndLastPositionOfElementInSortedArray {
    /**
     * <b>找边界问题 找target-1 和 target+1的位置。</b>
     * 排序的数组中查找元素，我们很容易想到用二分查找法。
     * 找到开始位置和结束位置的坐标。
     * 所以我们不是直接去找该元素的位置，而是去找这个元素的边界。
     * 我们以找右边界为例，我们的开始坐标就是找目标值-1的右边界，结束坐标就是目标值本身的右边界
     * */
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            // 这里减去1是为什么？通过演算过程可以知道答案
            int left = searchRight(nums,target-1);
            int right = searchRight(nums, target)- 1;
            return left > right ? new int[]{-1, -1} : new int[]{left, right};
        }

        private int searchRight(int[] nums, int target){
            int left = 0, right = nums.length - 1;
            while(left <= right){
                int mid = left + (right - left) / 2;
                // 说明右边界在右边
                if(nums[mid] <= target){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }
            return left;
        }
    }

    /**
     * 10:45 ~ 10:51
     * 用双指针法 时间复杂度为O(n)
     * */
    class Solution1{
        public int[] searchRange(int[] nums, int target) {
            int l = 0;
            int r = nums.length - 1;
            for (int i = 0; i < nums.length; i++) {
                if(target > nums[l]){
                    l++;
                }
                if(target < nums[r]){
                    r--;
                }
            }
            return l > r ? new int[]{-1, -1} : new int[]{l, r};
        }
    }
}
